Analog Computing
Analog computing uses physical phenomena (mechanical, electrical, etc.) to model problems of interest using physical quantities (pressures, voltages, position, etc.) to represent the variables in the problem, where the problem is some abstract mathematical problem or some physics problem involving other physical quantities. At its very simplest, an analog system (e.g., analog computer) solves a problem by taking one or more input variables of the problem, representing them as physical quantities, and then evolving their states in accordance with the laws of physics. The answer to the problem is produced as a physical variable that can then be read out.
There are two advantages to analog systems. The first is that operations are performed in a truly parallel manner. Since operations are normally governed by the laws of physics, there is nothing in the physics of most analog systems that prohibits one operation in one part of the analog system from occurring at the same time as another operation in another part of the analog system. The second advantage is that analog systems do not involve time-domain computations, and thus do not require the use of clocks. Many analog systems evolve in real time which, for most physical applications, is faster than performing the same calculations on a digital computer.
Traditionally, analog systems use some physical quantity (e.g., voltage, pressure, temperature, etc.) to represent a continuous variable. This leads to problems in accuracy, because the precision of the answer to the problem is limited by the precision to which the continuous variable can be quantified. This is the case because analog systems normally use physical quantities to represent the variables in a problem and physical quantities found in nature are inherently continuous. Digital computers, on the other hand, involve discriminating between the possible bit values “0” and “1”, for which there is an easy identification of the exact state. Analog systems are also often limited in the types of problems they can solve. For example, a sundial and a compass are both rudimentary analog computers. However, they can each only perform one operation, calculating the time based on the sun's position, and calculating the direction of the earth's magnetic field, respectively. A digital computer can be re-programmed to calculate both these problems using the same generic device. Analog systems are frequently more complex than digital computers. Further, the number of operations that an analog system can perform is often limited by the degree to which the circuits/devices can be duplicated.
Although digital computers are useful for solving many generic problems, there are still some problems whose solutions cannot be computed efficiently on a conventional digital computer. In other words, the time to find the solution to the problem does not scale polynomially with the size of the problem. In some cases, it is possible to parallelize the problem. However, such parallelization is often not practical from a cost perspective. Digital computers use a finite state machine approach. While the finite state machine approach works well for a broad class of computational problems, it imposes a fundamental limit on the complexity of the problems that can be solved. This is because the finite state machine approach uses a clock or timer to operate. Clocks implemented in current state of the art CMOS technology have a maximum clock rate (frequency) of about 5 GHz. In contrast, many analog systems do not require a clock. Thus answers to problems can evolve in a natural way in analog systems, often at a speed far greater, perhaps even exponentially greater, than their digital computing counterparts.
Digital computers have shown utility due to their low-power consumption, their discrete binary nature that makes state discrimination easy, and their ability to solve a broad array of general-purpose computational problems. However, many specific problems in quantum simulation, optimization, NP-hard and other NP-complete problems remain intractable on a digital computer. If the disadvantages of analog systems, such as their limited finite precision, could be overcome, an analog system could easily outperform a classical digital computer in solving important computational problems.
Complexity Classes
Computer scientists concerned with complexity routinely use the definitions of different complexity classes. The number of complexity classes is ever changing, as new ones are defined and existing ones merge through advancements made in computer science. The complexity classes known as polynomial-time (P), non-deterministic polynomial-time (NP), NP-complete (NPC), and NP-hard (NPH) are all classes of decision problems. Decision problems have binary outcomes.
Problems in NP are computational problems for which there exists polynomial time verification. That is, it takes no more than polynomial time (class P) in the size of the problem to verify a potential solution. It may take more than polynomial time to create a potential solution. For NP-hard problems it may take longer to verify a potential solution.
Problems in NPC can be defined as problems in NP that have been shown to be equivalent to, or harder to solve, than a known problem in NPC. Equivalently, the problems in NPC are problems in NP that are also in NPH. This can be expressed as NPC=NP∩NPH.
A problem is equivalent, or harder to solve, than a known problem in NPC if there exists a polynomial time reduction to the instant problem from the known problem in NPC. Reduction can be regarded as a generalization of mapping. The mappings can be one to one functions, many to one functions, or make use of oracles, etc. The concepts of complexity classes and how they define the intractability of certain computational problems is found in, for example, Garey and Johnson, 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, ISBN: 0716710455 pp. 1-15 (hereinafter “Garey and Johnson”). Also see, Cormen, Leiserson, and Rivest, 1990, Introduction to Algorithms, MIT Press, Cambridge, ISBN: 0262530910, pp. 964-985.
Often decision problems have a related optimization problem that is solved to determine the correct decision. Efficiency in solving a decision-based NP-complete problem will lead to efficiency in solving the corresponding optimization-based problem. This is generally true of any problem in NP. Often it is the optimization-based problem for which a solution is sought.
Quantum Devices
Quantum computing is a relatively new method of computing that uses quantum devices to take advantage of quantum effects, such as superposition of basis states and the entanglement of quantum devices, to perform certain computations faster than a classical digital computer. In digital computers, information is stored in bits, which can be in either a “0” or “1” state. For example, a bit may represent a logical “0” with a low voltage and a logical “1” with a high voltage. In contrast to the bits of a digital computer, a quantum computer stores information as qubits, a type of quantum device, in which data can be in either a “0” or “1” state, or in any superposition of these states,α|0>+β|1>.  (1)
In accordance with the terminology of equation (1), the “0” state of a digital computer is analogous to the |0> basis state of a qubit. Likewise, the “1” state of a digital computer is analogous to the |1> basis state of a qubit. In accordance with equation (1), a qubit permits a superposition of qubit basis states, where the qubit has a certain probability of being in either the |0> or |1> states. The term |α|2 is the probability of being in the |0> state and the term |β|2 is the probability of being in the |1> state, where |α|2+|β|2=1. Clearly, the continuous variables α and β contain a great deal more information than the states of bits in a digital computer, which are simply 0s or 1s. A qubit's state can be represented as the vector,
                              [                                                    α                                                                    β                                              ]                .                            (        2        )            Although the qubit can be in a linear combination (or superposition) of states, it can only be read out or measured as being in the |0> or |1> state. Quantum devices exhibit quantum behavior such as quantum tunneling between quantum basis states, superposition of basis states, entanglement of qubits, coherence, and the demonstration of both wave-like and particle-like properties. In a standard model of quantum computation (also known as the circuit model of quantum computation) quantum gate operations are performed on qubits in a quantum computing device in the time domain. In other words, individual gates operate on the state of one or more qubits in the quantum computing device for a predetermined period of time in order to effect a quantum computation. Gates are represented by matrices that are matrix multiplied with the state vector of the operated on qubits. The most elementary single-qubit gates are the Pauli matrices:
                              X          ≡                      [                                                            0                                                  1                                                                              1                                                  0                                                      ]                          ,                  Y          ≡                      [                                                            0                                                                      -                    i                                                                                                i                                                  0                                                      ]                          ,                  Z          ≡                                    [                                                                    1                                                        0                                                                                        0                                                                              -                      1                                                                                  ]                        .                                              (        3        )            Other single qubit gates include the Hadamard gate, the phase gate, and the π/8 gate. See, for example, Nielson and Chuang, 2000, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, pp. 174-177.
Two qubits coupled together also obey superposition:α00|00>+α01|01>+α10|10>+α11|11>.  (4)The state of a two-qubit system is represented by a four-element vector and two-qubit gate operations are represented by 4×4 matrices. An n qubit system is therefore represented by a 2n vector of continuous variables. A subset of elementary single gate operations, such as those shown in (3), and one or more two-qubit gate operations form a set of gates which are said to be universal for quantum computation. A universal set of quantum operations is any set of quantum operations that permits all possible quantum computations.Requirements for Quantum Computing
Generally speaking, a qubit is a well-defined physical structure that (i) has a plurality of quantum states, (ii) can be coherently isolated from its environment and (iii) permits quantum tunneling between two or more quantum states associated with the qubit. See for example, Mooji et al., 1999, Science 285, p. 1036 (hereinafter “Mooji”), which is hereby incorporated by reference herein in its entirety. A survey of the current physical systems from which qubits can be formed is found in Braunstein and Lo (eds.), 2001, Scalable Quantum Computers, Wiley-VCH, Berlin (hereinafter “Braunstein and Lo”) (also published as DiVincenzo, D., 2000, “The Physical Implementation of Quantum Computation,” arXiv.org: quant-ph/0002077).
In order for a physical system to behave as a qubit a number of requirements must be satisfied. See DiVincenzo in Braunstein and Lo, Chapter 1. These requirements include the need for the physical system (qubit) to be scalable. In other words, it must be possible to combine a reasonable number of the qubits in a coherent fashion. Associated with scalability is the need to eliminate qubit decoherence. Also required for a qubit to be useful in quantum computing, is the ability to perform operations that initialize, control and couple the qubit. Control of a qubit includes performing single qubit operations as well as operations on two or more qubits. In order to support quantum computing, this set of operations needs to be a universal set. Many sets of gates are universal, see, for example, Barenco et al., 1995, Physical Review A 52, p. 3457, which is hereby incorporated by reference herein in its entirety. Yet another requirement for quantum computing is the need to be able to measure the state of the qubit in order to perform computing operations and retrieve information. These requirements were developed for the circuit model of quantum computation and may be relaxed for other models.
Superconducting Qubits
Several quantum computing hardware proposals have been made. Of these hardware proposals, the most scalable physical systems appear to be those that are superconducting structures. Superconducting material is material that has no electrical resistance below critical levels of current, magnetic field and temperature. Josephson junctions are examples of such structures.
There are two principal means to realize superconducting qubits. One means corresponds to the limits of well-defined charge (charge qubit). The other means corresponds to the limits of well-defined phase (phase/flux qubit). Phase and charge are related variables that, according to basic quantum principles, are canonical conjugates of one another. The division of the two classes of devices is outlined in Makhlin et al., 2001, Reviews of Modern Physics 73, pp. 357-400 (hereinafter “Makhlin”), which is hereby incorporated herein by reference in its entirety. Superconducting qubits include devices that are well known in the art, such as Josephson junction qubits. See, for example, Barone and Paternò, 1982, Physics and Applications of the Josephson Effect, John Wiley and Sons, New York, pp. 416-427; Martinis et al., 2002, Physical Review Letters 89, 117901, which is hereby incorporated herein by reference in its entirety; and Han et al., 2001, Science 293, p. 1457, which is hereby incorporated herein by reference in its entirety.
Flux Qubits
One type of flux qubit is the persistent current qubit. See Orlando and Mooij et al., 1999, Physical Review B 60, 15398-15413 (hereinafter “Orlando”), which is hereby incorporated herein by reference in its entirety. The superconducting phase qubit is well known and has demonstrated long coherence times. See, for example, II'ichev et al., 2003, Physical Review Letters 91, 097906 (hereinafter “II'ichev”), which is hereby incorporated herein by reference in its entirety. Some other types of phase qubits comprise superconducting loops having more or less than three Josephson junctions. See, e.g., G. Blatter et al., 2001, Physical Review B, 63, 174511; and Friedman et al., 2000, Nature 406, 43 (hereinafter “Friedman 2000”), each of which is hereby incorporated herein by reference in its entirety. For more details on flux qubits, see U.S. Pat. Nos. 6,960,780 titled “Resonant controlled qubit system”; 6,897,468 titled “Resonant controlled qubit system”; 6,784,451 titled “Multi-junction phase qubit”; 6,885,325 titled “Sub-flux quantum generator”; 6,670,630 titled “Quantum phase-charge coupled device”; 6,822,255 titled “Finger squid qubit device”; 6,979,836 titled “Superconducting low inductance qubit”; U.S. Patent Application Publication Nos. 2004-0140537 titled “Extra-substrate control system”; 2004-0119061 titled “Methods for single qubit gate teleportation”; 2004-0016918 titled “System and method for controlling superconducting qubits; 2004-0000666 titled “Encoding and error suppression for superconducting quantum computers”; 2003-0173498 titled “Quantum phase-charge coupled device”; 2003-0169041 titled “Quantum computing integrated development environment”; 2003-0121028 titled “Quantum computing integrated development environment”; 2003-0107033 titled “Trilayer heterostructure junctions”; and 2002-0121636 titled “Quantum bit with a multi-terminal junction and loop with a phase shift” each of which is hereby incorporated herein by reference in its entirety.
FIG. 1A illustrates a superconducting phase qubit 100. Phase qubit 100 comprises a loop 103 of superconducting material interrupted by Josephson junctions 101-1, 101-2, and 101-3. Josephson junctions are typically formed using standard fabrication processes, generally involving material deposition and lithography stages. See, e.g., Madou, 2002, Fundamentals of Microfabrication, Second Edition, CRC Press, pp. 1-14. Methods of fabricating Josephson junctions are described, for example, in Ramos et al., 2001, IEEE Transactions on Applied Superconductivity 11, p. 998. Common substrates include silicon, silicon oxide, or sapphire, for example. Josephson junctions 101 can also include insulating materials such as aluminum oxide, for example. Examples of superconducting materials useful for forming superconducting loop 103 are aluminum and niobium. Josephson junctions 101 have sizes ranging from about 10 nanometers (nm) to about 10 micrometers (μm). One or more of the Josephson junctions 101 have parameters, such as the size of the junction, the junction surface area, the Josephson energy or the charging energy, that differ from the other Josephson junctions in phase qubit 100. The difference between any two Josephson junctions 101 in phase qubit 100 is characterized by a coefficient, termed α, which typically ranges from about 0.5 to about 1.3, where α=1 represents junctions with equivalent parameters. In some instances, the term α for a pair of Josephson junctions in the phase qubit is the ratio of the critical current of the respective Josephson junctions. The critical current of a Josephson junction is the current through the junction at which the junction is no longer superconducting. That is, below the critical current, the junction is superconducting, and above the critical current, the junction is not superconducting. Thus, for example, the term α for junctions 101-1 and 101-2 is defined as the ratio between the critical current of junction 101-1 and the critical current of junction 101-2.
Referring to FIG. 1A, a bias source 110 is inductively coupled to phase qubit 100. Bias source 110 is used to thread a magnetic flux Φx through phase qubit 100 to provide control of the state of the phase qubit. Phase qubit 100 typically operates with a magnetic flux bias Φx ranging between about 0.2·Φ0 to about 0.8·Φ0, where Φ0 is the flux quantum.
Phase qubit 100 has a simplified two-dimensional potential with respect to the phase across Josephson junctions 101. Phase qubit 100 is typically biased with a magnetic flux φx, such that the two-dimensional potential profile includes regions of local energy minima, where the local energy minima are separated from each other by small energy barriers and are separated from other regions by large energy barriers. This potential is a double well potential 150 (FIG. 1B) that includes a left well 160-0 and a right well 160-1, respectively representing clockwise 102-0 and counter-clockwise 102-1 circulating supercurrent in phase qubit 100 of FIG. 1A. A double well potential 150 can be formed when a flux bias of about 0.5·Φ0 is applied.
When wells 160-0 and 160-1 are at or near degeneracy, meaning that they are at the same or nearly the same energy potential as illustrated in FIG. 1B, the quantum state of phase qubit 100 becomes a coherent superposition of the phase or basis states and the device can be operated as a phase qubit. The point at or near degeneracy is herein referred to as the point of computational operation of phase qubit 100. During computational operation of phase qubit 100, controllable quantum effects can be used to process the quantum information stored in the phase states according to the rules of quantum computing. Since the quantum information stored and processed in the phase qubit is in the phase basis, it is insensitive to noise in the charge basis. II'ichev et al (II'ichev) used a three-Josephson junction flux qubit, coupled to a high-quality tank circuit, to perform a continuous observation of Rabi oscillations.
There are many problems with the standard model of quantum computation that make it a challenging feat of science and engineering. Quantum computing involves coherently processing quantum information. This requires sufficiently long decoherence times in the qubits, as well as immunity to noise and errors. Decoherence makes time-domain gate-level standard model quantum computation difficult. It is therefore desirable to harness quantum effects such as incoherent tunneling to solve useful problems, thus overcoming the challenges of standard model quantum computation.